﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace GraphTheory.Task1
{
    class Graph
    {
        private int size;
        private int[,] matrix;
        private int[] vertices;
        private double[,] floatMatrix;

        public Graph(string matrixString, GraphType type)
        {
            if (type == GraphType.UndirectedGraphFromString)
            {
                StringReader reader = new StringReader(matrixString);
                size = int.Parse(reader.ReadLine());
                matrix = new int[size, size];
                vertices = new int[size];

                for (int i = 0; i < size; i++)
                {
                    string line = reader.ReadLine();

                    for (int j = 0; j < size; j++)
                    {
                        matrix[i, j] = int.Parse(line[2 * j].ToString());
                    }
                }
            }
            else if (type == GraphType.UndirectedGraphFromFile)
            {
                Stream stream = File.OpenRead(matrixString);
                TextReader reader = new StreamReader(stream);

                size = int.Parse(reader.ReadLine());
                matrix = new int[size, size];
                vertices = new int[size];

                for (int i = 0; i < size; i++)
                {
                    string line = reader.ReadLine();

                    for (int j = 0; j < size; j++)
                    {
                        matrix[i, j] = int.Parse(line[2 * j].ToString());
                    }
                }
            }
            else if (type == GraphType.DirectedGraphFromString)
            {
                StringReader reader = new StringReader(matrixString);
                size = int.Parse(reader.ReadLine());
                floatMatrix = new double[size, size];
                vertices = new int[size];

                //bydlokod
                for (int i = 0; i < size; i++)
                {
                    string line = reader.ReadLine();

                    int stringStart = 0;
                    int currentEnd = 0;
                    int j = 0;
                    while (j < size)
                    {
                        while (currentEnd < line.Length && line[currentEnd] != ' ')
                        {
                            currentEnd++;
                        }
                        int tmp = 0;
                        if (int.TryParse(line.Substring(stringStart, currentEnd - stringStart), out tmp))
                        {
                            Console.WriteLine("'" + line.Substring(stringStart, currentEnd - stringStart) + "'");
                            floatMatrix[i, j++] = int.Parse(line.Substring(stringStart, currentEnd - stringStart));
                        }
                        else
                        {
                            Console.WriteLine("'" + line.Substring(stringStart, currentEnd - stringStart) + "'");
                            floatMatrix[i, j++] = double.NaN; ;
                        }
                        currentEnd++;
                        stringStart = currentEnd;
                    }
                }
                //end bydlokod
            }
        }
        public int CalculateNumberOfConnectedComponents()
        {
            for (int i = 0; i < size; i++)
            {
                vertices[i] = 0;
            }
            int n = 0;
            while (NotallVerticesAreCounted())
            {
                int currentVertex = vertices.ToList().IndexOf(0);
                TraverseConnectedComponent(currentVertex);
                n++;
            }
            return n;
        }

        private void TraverseConnectedComponent(int vertex)
        {

            bool setChanged = false;
            vertices[vertex] = 1;
            do
            {
                setChanged = false;
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        if (vertices[j] == 1 && matrix[j, i] == 1 && vertices[i] == 0)
                        {
                            vertices[i] = 1;
                            setChanged = true;
                        }
                    }
                }
            } while (setChanged);
        }

        private bool NotallVerticesAreCounted()
        {
            return !vertices.All(x => x == 1);
        }

        public int IsEuler()
        {
            if (CalculateNumberOfConnectedComponents() > 1)
            {
                return 1;
            }

            int currentVertex = 0;
            while (hasEdges())//&& CalculateNumberOfConnectedComponents() == 1)
            {
                if (VertexHasNoEdges(currentVertex))
                {
                    return 1;
                }
                for (int j = 0; j < size; j++)
                {
                    if (matrix[currentVertex, j] == 1)
                    {
                        if (EdgeIsBridge(currentVertex, j))
                        {
                            if (OtherEdgesExist(currentVertex, j))
                            {
                                continue;
                            }
                            else
                            {
                                matrix[currentVertex, j] = 0;
                                matrix[j, currentVertex] = 0;
                                currentVertex = j;
                                break;
                            }
                        }
                        else
                        {
                            matrix[currentVertex, j] = 0;
                            matrix[j, currentVertex] = 0;
                            currentVertex = j;
                            break;
                        }
                    }
                }
            }

            return currentVertex;
        }

        private bool OtherEdgesExist(int currentVertex, int j)
        {
            for (int i = j + 1; i < size; i++)
            {
                if (matrix[currentVertex, i] == 1)
                {
                    return true;
                }
            }
            return false;
        }

        private bool VertexHasNoEdges(int currentVertex)
        {
            for (int i = 0; i < size; i++)
            {
                if (matrix[currentVertex, i] == 1)
                    return false;
            }
            return true;
        }

        private bool EdgeIsBridge(int currentVertex, int k)
        {
            int initialNumberOfComponents = CalculateNumberOfConnectedComponents();
            int[,] matrixTemp = new int[size, size];
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    matrixTemp[i, j] = matrix[i, j];
                }
            }
            matrix[currentVertex, k] = 0;
            matrix[k, currentVertex] = 0;
            int newNumberOfConnectedComponents = CalculateNumberOfConnectedComponents();
            if (initialNumberOfComponents != newNumberOfConnectedComponents)
            {
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        matrix[i, j] = matrixTemp[i, j];
                    }
                }
                return true;
            }
            return false;
        }

        private bool hasEdges()
        {
            for (int i = 1; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (matrix[i, j] == 1)
                        return true;
                }
            }
            return false;
        }

        public bool IsChordal()
        {
            for (int i = 0; i < size; i++)
            {
                if (VertexIsAdjacentAbsorptive(i))
                {
                    return true;
                }
            }
            return false;
        }

        private bool VertexIsAdjacentAbsorptive(int i)
        {
            for (int j = 0; j < size; j++)
            {
                if (VertexIsAbsorptive(i, j) && matrix[i, j] == 1)
                {
                    return true;
                }
            }
            return false;
        }

        private bool VertexIsAbsorptive(int i, int j)
        {
            for (int k = 0; k < size; k++)
            {
                if (k != i && matrix[j, k] == 1)
                {
                    if (matrix[i, k] != 1)
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        internal string GetIndependentSet()
        {
            List<int> removed = new List<int>();
            bool ended = false;
            while (!ended)
            {
                ended = true;
                for (int i = 0; i < size; i++)
                {
                    if (VertexIsAdjacentAbsorptive(i))
                    {
                        for (int j = 0; j < size; j++)
                        {
                            matrix[i, j] = 0;
                            matrix[j, i] = 0;
                            removed.Add(i);
                            ended = false;
                        }
                    }
                }
            }
            string toReturn = string.Empty;
            for (int i = 0; i < size; i++)
            {
                if (!removed.Contains(i))
                {
                    toReturn += i.ToString();
                    toReturn += " ";
                }
            }
            return toReturn;
        }

        internal string GetColoring()
        {
            int[] colors = new int[size];

            PreColor(ref colors);
            bool gottaContinue = true;
            while (gottaContinue)
            {
                gottaContinue = false;
                int currentChromaticNumber = colors.Max();
                int vertexToRecolor = GetFirstNumber(colors, currentChromaticNumber);
                int vertexWithGreatestIndex = GetLatestAdjacent(vertexToRecolor);
                int prevColor = colors[vertexWithGreatestIndex];
                RecolorVertex(ref colors, vertexWithGreatestIndex);


                if (prevColor != colors[vertexWithGreatestIndex] && colors[vertexWithGreatestIndex] < currentChromaticNumber)
                {
                    try
                    {
                        RecolorAllSince(ref colors, vertexWithGreatestIndex + 1, currentChromaticNumber);
                        gottaContinue = true;
                    }
                    catch
                    {
                    }
                }

            }
            string toreturn = string.Empty;
            for (int i = 0; i < size; i++)
            {
                toreturn += i.ToString() + ": " + colors[i].ToString() + " ";
            }
            return toreturn;
        }

        private void RecolorAllSince(ref int[] colors, int p, int bannedColor)
        {
            for (int i = p; i < size; i++)
            {
                List<int> usedColors = new List<int>();
                for (int j = 0; j < size; j++)
                {
                    if (matrix[i, j] == 1)
                    {
                        usedColors.Add(colors[j]);
                    }
                }
                int colorToColor = 1;
                while (usedColors.Contains(colorToColor))
                {
                    colorToColor++;
                }
                if (colorToColor == bannedColor)
                {
                    throw new Exception("cant recolor");
                }
                colors[i] = colorToColor;
            }
        }

        private void RecolorVertex(ref int[] colors, int vertexWithGreatestIndex)
        {
            List<int> usedColors = new List<int>();
            for (int i = 0; i < size; i++)
            {
                if (matrix[vertexWithGreatestIndex, i] == 1)
                {
                    usedColors.Add(colors[i]);
                }
            }
            usedColors.Add(colors[vertexWithGreatestIndex]);
            int colorToColor = 1;
            while (usedColors.Contains(colorToColor))
            {
                colorToColor++;
            }
            if (colorToColor < colors.Max())
            {
                colors[vertexWithGreatestIndex] = colorToColor;
            }
        }

        private int GetLatestAdjacent(int vertexToRecolor)
        {
            for (int i = size - 1; i >= 0; i--)
            {
                if (matrix[vertexToRecolor, i] == 1)
                {
                    return i;
                }
            }
            throw new Exception("we have colored some shit");
        }

        private int GetFirstNumber(int[] colors, int currentChromaticNumber)
        {
            for (int i = 0; i < size; i++)
            {
                if (colors[i] == currentChromaticNumber)
                {
                    return i;
                }
            }
            throw new Exception("Some shit happened, array doesn't has it's max value");
        }

        private void PreColor(ref int[] colors)
        {
            colors[0] = 1;
            for (int i = 1; i < size; i++)
            {
                List<int> adjacentColors = new List<int>();
                for (int j = 0; j < size; j++)
                {
                    if (matrix[i, j] == 1 && colors[j] != 0)
                    {
                        adjacentColors.Add(colors[j]);
                    }
                }
                int colorToColor = 1;
                while (adjacentColors.Contains(colorToColor))
                {
                    colorToColor++;
                }
                colors[i] = colorToColor;
            }
        }

        internal string BellmanFord()
        {
            double[,] A = new double[size, size * (size - 1)];
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size * (size - 1); j++)
                {
                    A[i, j] = double.PositiveInfinity;
                }
            }

            A[0, 0] = 0;
            for (int i = 1; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    for (int k = 0; k < size; k++)
                    {
                        if (!double.IsNaN(floatMatrix[j, k]))
                        {
                            if (A[k, i] > A[j, i - 1] + floatMatrix[j, k])
                            {
                                A[k, i] = A[j, i - 1] + floatMatrix[j, k];

                            }
                        }
                    }
                }
            }
            string toReturn = "\n";
            for (int i = 0; i < size; i++)
            {
                double currentMin = double.PositiveInfinity;
                for (int j = 0; j < size; j++)
                {
                    if (currentMin > A[i, j] && A[i, j] != double.PositiveInfinity)
                    {
                        currentMin = A[i, j];
                    }
                }
                toReturn += "0->" + (i).ToString() + ": " + (currentMin).ToString() + ";\n";
            }
            return toReturn;
        }

        internal string FloydWorshell()
        {
            double[,] W = new double[size, size];
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (!double.IsNaN(floatMatrix[i, j]))
                    {
                        W[i, j] = floatMatrix[i, j];
                    }
                    else
                    {
                        W[i, j] = double.PositiveInfinity;
                    }
                }
            }
            for (int k = 0; k < size; k++)
            {
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        W[i, j] = Math.Min(W[i, j], W[i, k] + W[k, j]);
                    }
                }
            }
            string toReturn = string.Empty;
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    toReturn += i.ToString() + "->" + j.ToString() + ": " + W[i, j] + "\n";
                }
            }
            return toReturn;
        }
    }
}
